package com.phy.kim.foroffer;

/**
 * @author RiceDoggyRoll
 */
public class Offer003CountBits {

  public static void main(String[] args) {
    int[] ints = new Offer003CountBits().countBits(7);
    for (int i = 0; i < ints.length; i++) {
      System.out.println(ints[i]);
    }
  }

  public int[] countBits1(int n) {
    int[] bits = new int[n + 1];
    for (int i = 0; i <= n; i++) {
      bits[i] = countOnes(i);
    }
    return bits;
  }

  public int countOnes(int x) {
    int ones = 0;
    while (x > 0) {
      ones += (x & 1);
      x = x >> 1;
    }
    return ones;
  }

  public int[] countBits2(int n) {
    //dp[i] = dp[i-1]，当i为奇数
    //dp[i] = dp[i/2]，当i为偶数
    //dp[i] = dp[i/2] + i % 2
    int[] bits = new int[n + 1];
    for (int i = 0; i <= n; i++) {
      bits[i] = bits[i >> 1] + (i & 1);
    }
    return bits;
  }

  public int[] countBits(int n) {
    //动态规划
    int[] bits = new int[n + 1];
    int highBit = 0;
    for (int i = 1; i <= n; i++) {
      if ((i & (i - 1)) == 0) {
        highBit = i;
      }
      bits[i] = bits[i - highBit] + 1;
    }
    return bits;
  }

}
